{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Clone N-ary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cloneTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #克隆 N 叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵 N 叉树的根节点&nbsp;<code>root</code>&nbsp;，返回该树的<a href=\"https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin\"><strong>深拷贝</strong></a>（克隆）。</p>\n",
    "\n",
    "<p>N 叉树的每个节点都包含一个值（ <code>int</code>&nbsp;）和子节点的列表（ <code>List[Node]</code>&nbsp;）。</p>\n",
    "\n",
    "<pre>\n",
    "class Node {\n",
    "    public int val;\n",
    "    public List&lt;Node&gt; children;\n",
    "}\n",
    "</pre>\n",
    "\n",
    "<p><em>N 叉树的输入序列用层序遍历表示，每组子节点用 null 分隔（见示例）。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png\" style=\"width:330px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,3,2,4,null,5,6]\n",
    "<strong>输出：</strong>[1,null,3,2,4,null,5,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png\" style=\"height:241px; width:296px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "<strong>输出：</strong>[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给定的 N 叉树的深度小于或等于&nbsp;<code>1000</code>。</li>\n",
    "\t<li>节点的总个数在&nbsp;<code>[0,&nbsp;10^4]</code>&nbsp;之间</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你的解决方案可以适用于<a href=\"https://leetcode-cn.com/problems/clone-graph/\">克隆图</a>问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [clone-n-ary-tree](https://leetcode.cn/problems/clone-n-ary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [clone-n-ary-tree](https://leetcode.cn/problems/clone-n-ary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,3,2,4,null,5,6]', '[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "import copy\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        def clone(node, par, is_root=False):\n",
    "            if node is None:\n",
    "                return None\n",
    "            new_node = Node(node.val)\n",
    "            if not is_root:\n",
    "                par.children.append(new_node)\n",
    "            for nd in node.children:\n",
    "                clone(nd, new_node)\n",
    "            return new_node\n",
    "\n",
    "        return clone(root, None, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None  \n",
    "        rt = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            rt.children.append(self.cloneTree(ch))\n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        node = Node(val=root.val)\n",
    "        node.children = [self.cloneTree(child_node) for child_node in root.children]\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "\n",
    "        def dfs(copied: Optional[Node]):\n",
    "            if copied is None:\n",
    "                return None\n",
    "            \n",
    "            target_children = []\n",
    "            for child in copied.children:\n",
    "                target_children.append(dfs(child))\n",
    "            \n",
    "            return Node(copied.val, target_children)\n",
    "        \n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        new_root = Node(root.val, [])\n",
    "        self._clone(root, new_root)\n",
    "        return new_root\n",
    "        \n",
    "    \n",
    "    def _clone(self, root, new_root):\n",
    "        if root is None:\n",
    "            return \n",
    "        \n",
    "        for c in root.children:\n",
    "            new_child = Node(c.val, [])\n",
    "            new_root.children.append(new_child)\n",
    "            self._clone(c, new_child)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        ans = Node(root.val)\n",
    "\n",
    "        queue, queue_copy = [root], [ans]\n",
    "        while queue:\n",
    "            head_node = queue.pop(0)\n",
    "            curr = queue_copy.pop(0)\n",
    "            for node in head_node.children:\n",
    "                copy_node = Node(node.val)\n",
    "                curr.children.append(copy_node)\n",
    "                queue.append(node)\n",
    "                queue_copy.append(copy_node)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        def clone(node):\n",
    "            return Node(node.val, [clone(child) for child in node.children])\n",
    "        return clone(root) if root else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return \n",
    "        node = Node(root.val)\n",
    "        children = []\n",
    "        for child in root.children:\n",
    "            children.append(self.cloneTree(child))\n",
    "        node.children = children\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root != None:\n",
    "            node = Node(root.val)\n",
    "            for i in root.children:\n",
    "                node.children.append(self.cloneTree(i))\n",
    "            return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        new_root = Node(root.val)\n",
    "\n",
    "        queue, queue_copy = [root], [new_root]\n",
    "        while queue:\n",
    "            head_node = queue.pop(0)\n",
    "            curr = queue_copy.pop(0)\n",
    "            for node in head_node.children:\n",
    "                copy_node = Node(node.val)\n",
    "                curr.children.append(copy_node)\n",
    "                \n",
    "                queue.append(node)\n",
    "                queue_copy.append(copy_node)\n",
    "        return new_root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None\n",
    "        root_clone = Node(root.val)\n",
    "\n",
    "        for child in root.children:\n",
    "            root_clone.children.append(self.cloneTree(child))\n",
    "\n",
    "        return root_clone\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # return copy.deepcopy(root)\n",
    "\n",
    "\n",
    "\n",
    "        # if root == None:\n",
    "        #     return None\n",
    "        # root_clone = Node(root.val)\n",
    "\n",
    "        # q1 = [root]\n",
    "        # q2 = [root_clone]\n",
    "\n",
    "        # while q1:\n",
    "        #     cur1 = q1.pop(0)\n",
    "        #     cur2 = q2.pop(0)\n",
    "\n",
    "        #     for n in cur1.children:\n",
    "        #         q1.append(n)\n",
    "\n",
    "        #         temp = Node(n.val)\n",
    "        #         cur2.children.append(temp)\n",
    "        #         q2.append(temp)\n",
    "\n",
    "        # return root_clone"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        r_stack = [root]\n",
    "        ret = Node(root.val)\n",
    "        w_stack = [ret]\n",
    "        while r_stack:\n",
    "            rnode = r_stack.pop(0)\n",
    "            wnode = w_stack.pop(0)\n",
    "            for sn in rnode.children:\n",
    "                r_stack.append(sn)\n",
    "                tmp = Node(sn.val)\n",
    "                wnode.children.append(tmp)\n",
    "                w_stack.append(tmp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None\n",
    "        rt = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            rt.children.append(self.cloneTree(ch))\n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        node = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            node.children.append(self.cloneTree(ch))\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "            rt = Node(root.val)\n",
    "            for ch in root.children:\n",
    "                rt.children.append(dfs(ch))\n",
    "            return rt\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None\n",
    "        rt = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            rt.children.append(self.cloneTree(ch))\n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "\n",
    "        def dfs(node):\n",
    "\n",
    "            if not node:\n",
    "                return None\n",
    "\n",
    "            cur_children = []\n",
    "            for i in range(len(node.children)):\n",
    "                cur_children.append(dfs(node.children[i]))\n",
    "\n",
    "            return Node(node.val,cur_children)\n",
    "\n",
    "        return dfs(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None\n",
    "        root_clone = Node(root.val)\n",
    "\n",
    "        q1 = [root]\n",
    "        q2 = [root_clone]\n",
    "\n",
    "        while q1:\n",
    "            cur1 = q1.pop(0)\n",
    "            cur2 = q2.pop(0)\n",
    "\n",
    "            for n in cur1.children:\n",
    "                q1.append(n)\n",
    "\n",
    "                temp = Node(n.val)\n",
    "                cur2.children.append(temp)\n",
    "                q2.append(temp)\n",
    "\n",
    "        return root_clone"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None\n",
    "        rt = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            rt.children.append(self.cloneTree(ch))\n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "\n",
    "        def method(node):\n",
    "            if node==None:\n",
    "                return\n",
    "            else:\n",
    "                new_node=Node()\n",
    "                new_node.val=node.val\n",
    "                for child in node.children:\n",
    "                    new_node.children.append(method(child))\n",
    "                return new_node\n",
    "\n",
    "        ret=method(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root!=None:\n",
    "            node=Node(root.val)\n",
    "            for i in root.children:\n",
    "                node.children.append(self.cloneTree(i))\n",
    "            return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        new_node = Node(root.val, [])\n",
    "        for child in root.children:\n",
    "            new_child = self.cloneTree(child)\n",
    "            new_node.children.append(new_child)\n",
    "        \n",
    "        return new_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        node = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            node.children.append(self.cloneTree(ch))\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "      if not root:\n",
    "        return None\n",
    "      \n",
    "      newRoot = Node(root.val)\n",
    "      for nex in root.children:\n",
    "        newRoot.children.append(self.cloneTree(nex))\n",
    "      return newRoot\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "      if not root:\n",
    "        return None\n",
    "      \n",
    "      newRoot = Node(root.val)\n",
    "      for nex in root.children:\n",
    "        newRoot.children.append(self.cloneTree(nex))\n",
    "      return newRoot\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        def clone(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            return Node(node.val, [clone(child) for child in node.children])\n",
    "        return clone(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        new_root = Node(root.val, [])\n",
    "        for i in root.children:\n",
    "            new_root.children.append(self.cloneTree(i))\n",
    "        return new_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None\n",
    "        rt = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            rt.children.append(self.cloneTree(ch))\n",
    "        return rt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "         # 如果为空树，直接返回None\n",
    "        if not root:\n",
    "            return\n",
    "        # 先拷贝一个根节点\n",
    "        self.root = Node(root.val)\n",
    "        # 创建两个队列，用于同步BFS\n",
    "        que = collections.deque()\n",
    "        que_copy = collections.deque()\n",
    "        # 将两个根节点分别入队\n",
    "        que.append(root)\n",
    "        que_copy.append(self.root)\n",
    "        # 开始BFS\n",
    "        while que:\n",
    "            # 取出对首节点\n",
    "            head_node = que.popleft()\n",
    "            cur = que_copy.popleft()\n",
    "            for node in head_node.children:\n",
    "                # 拷贝孩子节点\n",
    "                cp_node = Node(node.val)\n",
    "                cur.children.append(cp_node)\n",
    "                # 将孩子节点入队\n",
    "                que.append(node)\n",
    "                que_copy.append(cp_node)\n",
    "\n",
    "        return self.root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        # 如果为空树，直接返回None\n",
    "        if not root:\n",
    "            return\n",
    "        # 先拷贝一个根节点\n",
    "        self.root = Node(root.val)\n",
    "        # 创建两个队列，用于同步BFS\n",
    "        que = collections.deque()\n",
    "        que_copy = collections.deque()\n",
    "        # 将两个根节点分别入队\n",
    "        que.append(root)\n",
    "        que_copy.append(self.root)\n",
    "        # 开始BFS\n",
    "        while que:\n",
    "            # 取出对首节点\n",
    "            head_node = que.popleft()\n",
    "            cur = que_copy.popleft()\n",
    "            for node in head_node.children:\n",
    "                # 拷贝孩子节点\n",
    "                cp_node = Node(node.val)\n",
    "                cur.children.append(cp_node)\n",
    "                # 将孩子节点入队\n",
    "                que.append(node)\n",
    "                que_copy.append(cp_node)\n",
    "\n",
    "        return self.root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        new_root = self.helper(root)\n",
    "        return new_root\n",
    "\n",
    "    def helper(self, original_node):\n",
    "        if not original_node:\n",
    "            return None\n",
    "        new_root = Node(original_node.val)\n",
    "        children_lst = []\n",
    "        for c in original_node.children:\n",
    "            clone_child = self.helper(c)\n",
    "            children_lst.append(clone_child)\n",
    "        new_root.children = children_lst\n",
    "        return new_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        ########## dfs最简单\n",
    "        if root == None:\n",
    "            return None\n",
    "        rt = Node(root.val)\n",
    "        for ch in root.children:\n",
    "            rt.children.append(self.cloneTree(ch))\n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root: return root\n",
    "        self.root = Node(root.val)\n",
    "        que = collections.deque()\n",
    "        cp_que = collections.deque()\n",
    "\n",
    "        que.append(root)\n",
    "        cp_que.append(self.root)\n",
    "\n",
    "        while que:\n",
    "            head_node = que.popleft()\n",
    "            cur = cp_que.popleft()\n",
    "            for node in head_node.children:\n",
    "                cp_node = Node(node.val)\n",
    "                cur.children.append(cp_node)\n",
    "                que.append(node)\n",
    "                cp_que.append(cp_node)\n",
    "    \n",
    "        return self.root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        def clone(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            \n",
    "            children = []\n",
    "            for child in node.children:\n",
    "                children.append(clone(child))\n",
    "            new_node = Node(node.val, children)\n",
    "            return new_node\n",
    "        return clone(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "# class Solution:\n",
    "#     def cloneTree(self, root: 'Node') -> 'Node':\n",
    "#         # 递归实现，dfs版本\n",
    "#         if root == None:\n",
    "#             return\n",
    "#         clone_root = Node(root.val)\n",
    "#         for ch in root.children:\n",
    "#             clone_root.children.append(self.cloneTree(ch))\n",
    "#         return clone_root       \n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        # 递归实现，bfs版本\n",
    "        if root == None:\n",
    "            return\n",
    "        clone_root = Node(root.val)\n",
    "        q1 = [root]\n",
    "        q2 = [clone_root]\n",
    "        while q1:\n",
    "            rt = q1.pop(0)\n",
    "            crt = q2.pop(0)\n",
    "            for ch in rt.children:\n",
    "                q1.append(ch)\n",
    "\n",
    "                clone_ch = Node(ch.val)\n",
    "                crt.children.append(clone_ch)\n",
    "                q2.append(clone_ch)\n",
    "        return clone_root       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return root\n",
    "        new_root = Node(root.val)\n",
    "        dq1 = deque([root])\n",
    "        dq2 = deque([new_root])\n",
    "        while dq1:\n",
    "            for _ in range(len(dq1)):\n",
    "                cur = dq1.popleft()\n",
    "                cpy = dq2.popleft()\n",
    "                for it in cur.children:\n",
    "                    tmp = Node(it.val)\n",
    "                    cpy.children.append(tmp)\n",
    "                    dq1.append(it)\n",
    "                    dq2.append(tmp)\n",
    "        return new_root\n",
    "\n",
    "    def cloneTree2(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return root\n",
    "        mapping = dict()\n",
    "        new_root = Node(root.val)\n",
    "        mapping[root] = new_root\n",
    "\n",
    "        def dfs(root):\n",
    "            for it in root.children:\n",
    "                tmp_node = Node(it.val)\n",
    "                mapping[it] = tmp_node\n",
    "                mapping[root].children.append(tmp_node)\n",
    "                dfs(it)\n",
    "\n",
    "        dfs(root)\n",
    "        return new_root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        mapping = {}\n",
    "        mapping[root] = Node(root.val, [])\n",
    "        queue = deque([root])\n",
    "        \n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.children:\n",
    "                    for child in node.children:\n",
    "                        mapping[child] = Node(child.val, [])\n",
    "                        mapping[node].children.append(mapping[child])\n",
    "                        queue.append(child)\n",
    "        return mapping[root]         \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root: return root\n",
    "        self.root = Node(root.val)\n",
    "        que = collections.deque()\n",
    "        que_copy = collections.deque()\n",
    "\n",
    "        que.append(root)\n",
    "        que_copy.append(self.root)\n",
    "\n",
    "        while que:\n",
    "            head_node = que.popleft()\n",
    "            cur = que_copy.popleft()\n",
    "            for node in head_node.children:\n",
    "                cp_node = Node(node.val)\n",
    "                cur.children.append(cp_node)\n",
    "                que.append(node)\n",
    "                que_copy.append(cp_node)\n",
    "    \n",
    "        return self.root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        # 如果为空树，直接返回None\n",
    "        if not root:\n",
    "            return\n",
    "        # 先拷贝一个根节点\n",
    "        self.root = Node(root.val)\n",
    "        # 创建两个队列，用于同步BFS\n",
    "        que = collections.deque()\n",
    "        que_copy = collections.deque()\n",
    "        # 将两个根节点分别入队\n",
    "        que.append(root)\n",
    "        que_copy.append(self.root)\n",
    "        # 开始BFS\n",
    "        while que:\n",
    "            # 取出对首节点\n",
    "            head_node = que.popleft()\n",
    "            cur = que_copy.popleft()\n",
    "            for node in head_node.children:\n",
    "                # 拷贝孩子节点\n",
    "                cp_node = Node(node.val)\n",
    "                cur.children.append(cp_node)\n",
    "                # 将孩子节点入队\n",
    "                que.append(node)\n",
    "                que_copy.append(cp_node)\n",
    "\n",
    "        return self.root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root: return\n",
    "        res_root = Node(root.val)\n",
    "        q = deque()\n",
    "        q_tmp = deque()\n",
    "        q.append(root)\n",
    "        q_tmp.append(res_root)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            cur_tmp = q_tmp.popleft()\n",
    "            for node in cur.children:\n",
    "                cp_node = Node(node.val)\n",
    "                cur_tmp.children.append(cp_node)\n",
    "                q.append(node)\n",
    "                q_tmp.append(cp_node)\n",
    "        \n",
    "        return res_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        newroot = Node(root.val,[])\n",
    "        q = collections.deque([(root,newroot)])\n",
    "        while q:\n",
    "            node,newnode = q.popleft()\n",
    "            if node:\n",
    "                for child in node.children:\n",
    "                    newchild = Node(child.val,[])\n",
    "                    newnode.children.append(newchild)\n",
    "                    q.append([child,newchild])\n",
    "        return newroot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\r\n",
    "# Definition for a Node.\r\n",
    "class Node:\r\n",
    "    def __init__(self, val=None, children=None):\r\n",
    "        self.val = val\r\n",
    "        self.children = children if children is not None else []\r\n",
    "\"\"\"\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\r\n",
    "        ########## dfs最简单\r\n",
    "        if root == None:\r\n",
    "            return None\r\n",
    "        rt = Node(root.val)\r\n",
    "        for ch in root.children:\r\n",
    "            rt.children.append(self.cloneTree(ch))\r\n",
    "        return rt\r\n",
    "        \r\n",
    "    def cloneTree2(self, root: 'Node') -> 'Node':\r\n",
    "        ########## bfs\r\n",
    "        if root == None:\r\n",
    "            return None\r\n",
    "        rt = Node(root.val)\r\n",
    "\r\n",
    "        q1 = [root]\r\n",
    "        q2 = [rt]\r\n",
    "        while q1:\r\n",
    "            cur1 = q1.pop(0)\r\n",
    "            cur2 = q2.pop(0)\r\n",
    "            for ch in cur1.children:\r\n",
    "                q1.append(ch)\r\n",
    "\r\n",
    "                tmp = Node(ch.val)\r\n",
    "                cur2.children.append(tmp)\r\n",
    "                q2.append(tmp)\r\n",
    "\r\n",
    "        return rt\r\n",
    "        \r\n",
    "\r\n",
    "    def cloneTree3(self, root: 'Node') -> 'Node':\r\n",
    "        ### 递归\r\n",
    "        if root:\r\n",
    "            return Node(root.val, list(map(self.cloneTree3, root.children)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        newroot = Node(root.val,[])\n",
    "        q = collections.deque([(root,newroot)])\n",
    "        while q:\n",
    "            node,newnode = q.popleft()\n",
    "            if node:\n",
    "                for child in node.children:\n",
    "                    newchild = Node(child.val,[])\n",
    "                    newnode.children.append(newchild)\n",
    "                    q.append([child,newchild])\n",
    "        return newroot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        queue = deque([root])\n",
    "        mapping = {}\n",
    "        mapping[root] = Node(root.val, [])\n",
    "        \n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.children:\n",
    "                    for child in node.children:\n",
    "                        mapping[child] = Node(child.val, [])\n",
    "                        mapping[node].children.append(mapping[child])\n",
    "                        queue.append(child)\n",
    "        return mapping[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneTree(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return root\n",
    "        root2 = Node(root.val)\n",
    "        queue = [(root,root2)]\n",
    "        while queue:\n",
    "            node1, node2 = queue.pop(0)\n",
    "            tmp = []\n",
    "            for children in node1.children:\n",
    "                node = Node(children.val)\n",
    "                tmp.append(node)\n",
    "                queue.append((children, node))\n",
    "            node2.children = tmp\n",
    "        return root2\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
